The present invention relates to a method and system for visualizing data and data objects. More specifically, the present invention pertains to a method and system for computing forces on data objects in physics-based visualization techniques.
The analysis of data objects can be facilitated by displaying them in multi-dimensional space. By displaying data objects in this manner, it is easier to visualize the relationships between the data objects while preserving the essential information in the data.
One technique known in the art for computing the layout of data objects in multi-dimensional space is generally referred to as a physics-based visualization system. Data objects are positioned in xe2x80x9cspacexe2x80x9d according to how strongly the data objects are related. The relationship between data objects is characterized according to their xe2x80x9csimilarityxe2x80x9d or xe2x80x9cconfidence levelxe2x80x9d and their xe2x80x9csupport.xe2x80x9d Similarity (confidence level) and support are best defined by way of a market basket example: if 85 percent of the customers who bought a printer also bought paper, and 10 percent of all customers bought both a printer and paper, then similarity is 85 percent and support is 10 percent. Note that similarity is directional; that is, although 85 percent of the customers who bought a printer also bought paper, it is not necessarily true that 85 percent of the customers who bought paper also bought a printer.
In multi-dimensional space, the distance between a pair of data objects indicates their degree of support; the closer the objects, the greater their degree of support. The similarity between data objects is represented by a xe2x80x9clinkxe2x80x9d or an xe2x80x9cedgexe2x80x9d between the objects. A link or edge is essentially a line between two data objects that have a degree of similarity that is greater than zero. The color of the link (edge) can be used to indicate the degree of similarity. Also, the link may include an arrow to show the direction of the association.
Physics-based visualization systems execute in a known manner to place data objects such that the distance between any two data objects is indicative of the degree of support between those two objects. Much as stars and planets exert forces on each other in astrophysical space, data objects in visualization space can be thought of as exerting xe2x80x9cforcesxe2x80x9d on each other. In essence, these forces should be proportionate with the degree of support between each data object and the other data objects in the system. Data objects with higher degrees of support should exert higher forces on each other and thus should be placed closer together.
Thus, in a physics-based visualization system, one of the key procedures for determining the final placement of data objects is to calculate the forces applied to each data object by the other data objects in the system. To calculate the force for every data object, the simplistic approach is to compute the force for every possible pairing of data objects, and sum the results. However, this would result in a run time on the order of N2 for a system of N data objects. Thus, the simplistic approach is computationally very expensive and can take a long time to complete, and so it is desirable to find a more efficient way of calculating the forces applied to each data object.
In astrophysics, techniques known in the art can be used to accelerate the force computations. One such technique, referred to herein as xe2x80x9cBarnes-Hut,xe2x80x9d is described in J. E. Barnes and P. Hut (1986), xe2x80x9cA Hierarchical O(N log N) Force-Calculation Algorithm,xe2x80x9d Nature, 324(6270) (pages 446-449), hereby incorporated by reference. Instead of a run time on the order of N2, the Barnes-Hut technique reduces run time to the order of N log N.
Techniques such as Barnes-Hut generally represent objects that are far away as a single, heavier object. For example, to calculate the force of a distant galaxy on a single star, the force is calculated considering the galaxy as a whole, rather than by calculating the force exerted by each individual star in the galaxy and summing the results.
In astrophysics, the force between objects is a function of the distance between the objects, and so the approximations introduced by Barnes-Hut can be readily applied. However, in physics-based visualization systems, the force between data objects is a function not only of the distance between objects (their degree of support), but also the similarity between objects. Because forces in a physics-based visualization system are dependent on both the distance between data objects and the similarity of the data objects, applying a computationally efficient force computation technique such as Barnes-Hut is problematic. This problem is illustrated by Prior Art FIG. 1.
Prior Art FIG. 1 shows data objects 10, 12, 14, 16 and 18 represented in two-dimensional space. Here, similarity between data objects is represented as a normalized value between zero and one, with a value of zero indicating that there is no similarity and a value of one indicating the maximum degree of similarity. The object pairs 10 and 12, 14 and 16, and 16 and 18 each have a degree of similarity greater than (not equal to) zero, while the other object pairs (e.g., 10 and 14, 10 and 16, and so on) have a degree of similarity equal to zero. In FIG. 1, a line (e.g., a link or edge) between data objects indicates that they are similar to some degree, while the absence of a line indicates a similarity of zero.
When calculating the force exerted on data object 12 using the Barnes-Hut technique, for example, data objects 14 and 16 can be represented as a single object, because these objects are far enough away from data object 12 while relatively close to each other. When calculating the force exerted on data object 18, it is desirable to employ the same optimization; that is, it is desirable to represent data objects 14 and 16 as a single object. However, because in physics-based visualization systems the force between data objects is a function not only of the distance between objects but also the similarity between objects, the force exerted by data objects 14 and 16 on data object 12 are different from the force exerted by data objects 14 and 16 on data object 18. Thus, application of computationally efficient force computation techniques such as Barnes-Hut to physics-based visualization systems is problematic because techniques such as Barnes-Hut implement optimizations that are dependent only on the distance between objects while physics-based visualization systems are dependent on more than one parameter (e.g., distance and similarity).
Accordingly, what is needed is a method and/or system for accelerating calculations of force in physics-based visualization systems. What is also needed is a method and/or system that can satisfy this need and that can account for the similarity between data objects. The present invention provides a novel solution to these needs.
A method and system thereof for computing forces on data objects in a physics-based visualization system are described. First forces exerted on a data object by other data objects in the plurality are determined without considering the similarity between data objects. Second forces exerted on the data object by a portion of the other data objects, each data object in the portion having a degree of similarity to the data object, are determined considering the similarity between data objects. The first forces are adjusted using the second forces to determine a net force on the data object. The net force is thus determined without having to consider similarity between all data objects in the plurality.